Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The massive amount of digital data stored in an optical disk storage increases the probability of the errors. To correct the errors, error control coding is used. Reference is now made to FIG. 1, wherein an error correction system comprises an encoding section 21, which transforms an input information sequence entered on the optical disk storage into code words.
In optical disk applications the code words are encoded based on International Standard Organization (ISO) Standard that requires Cyclic Redundancy Check (CRC) encoding and incorporates a Reed-Solomon (RS) code over some Galois fields.
The RS (m,k) code is a cyclic symbol error-correcting code where k symbols of an original data are encoded. The result, which is an (m-k)-symbol redundancy block, is appended to the data.
The Galois field is a finite field, the elements of which may be represented as polynomials in a particular primitive element. The RS code represents a block sequence of a Galois field GF(2.sup.n) of 2.sup.n binary symbols, where n is the number of bits per symbol. Constructing the Galois field GF(2.sup.n) requires a generator polynomial p(x) of degree n and a primitive element .beta., which is a root of p(x). The powers of B generate all nonzero elements of GF(2.sup.n). Encoding and decoding circuitry is therefore required which has a capability of performing Galois field arithmetic.
The encoding section 21 comprises a CRC encoder 22 for CRC encoding input data entered on the optical disk and a RS encoder 23 for RS encoding the input data. According to the ISO requirement, the CRC encoder 22 generates four CRC redundancy bytes. The RS encoder 23 generates, in k steps, (m-k) redundancy bytes, which are appended to the original code data to make a m-byte code word. A writing unit 24 records the coded data on an optical disk 25.
A reading unit 26 unloads data from the optical disk 25 and transfers them to a decoding section 27. The decoding section 27 comprises a syndrome generator 28 for decoding the RS code and a CRC decoder 29 for checking the CRC redundancy bytes. The syndrome generator 28 calculates the syndrome for each word received from the optical disk. The syndrome is the (m-k)-bit vector, which is actually the remainder that results from dividing an error polynomial by the original generator polynomial. Therefore, the syndrome helps to locate errors and calculate error values.
The CRC decoder 29 provides the redundancy check corresponding to the CRC encoding. Due to the operational similarity in the CRC encoding and decoding, the CRC encoder 22 and CRC decoder 29 usually share the same circuitry.
For error correction, circuitry capable of correcting a maximum of 8 bytes for every 120 byte code word, used in an optical disk storage, a shortened RS (120,104) code over the Galois field GF(2.sup.8) is required. This field consists of 256 vectors which represent every number between and including 0 to 255. These vectors are referenced using a specific element .alpha..sup.i, where i=0, 1, . . . , 255.
In order to generate GF(2.sup.8), a generator polynomial p(x) of degree 8 (e.g. p(x)=1+x.sup.2 +x.sup.3 +x.sup.5 +x.sup.8) and a primitive element .beta..sup.j are required. The primitive element .beta..sup.j can be used to generate another field by the same polynomial. The j represents a number coprime to (2.sup.n -1) for GF(2.sup.n), i.e. a number which is not divisible by (2.sup.n -1) or any of its factors. For GF(2.sup.8), there are 128 different primitive elements .beta..sup.j, which can be used to generate various fields from each particular generator polynomial.
To implement their functions, each of the above indicated encoding and decoding elements requires a plurality of unary multipliers for multiplying by field elements in a Galois field. Each of the multipliers corresponds to the specific field element .alpha..sup.i. Each unary multiplier consists of a plurality of Exclusive-OR (XOR) gates. The number of the XOR gates is a determining factor for the total signal delay of the error correction circuit. Reduction of the signal delay would allow to increase the processing speed of the error correction circuit.
In view of the above, it would be desirable to provide a system for correcting errors in optical disks, wherein the fewest number of the XOR gates could be used.